package leetcode.code0128;

/**
 * Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
 * @author CaoYu
 * @date 2021年11月7日
 * @description
 */
public class Solution1 extends Solution128 {

	private final int OFF = (int) 10e9;
	private final int SIZE = (OFF >> 1) + 1;
	private int[] p;
	private int[] s;
	private int[] stack;
	private int max;

	@Override
	public int longestConsecutive(int[] nums) {
		if (nums.length == 0)
			return 0;
		this.p = new int[SIZE];
		this.s = new int[SIZE];
		this.stack = new int[SIZE];
		this.max = 1;
		for (int num : nums) {
			int representNum = this.findRepresent(num);// 找到num的代表数
			Integer representLast = this.findNext2Num(num - 1);// 找num上一个数的代表，null没有
			Integer representNext = this.findNext2Num(num + 1);// 找num下一个数的代表，null没有
			if (representLast != null && representNum != representLast) {
				this.merge(representNum, representLast);
			}
			if (representNext != null && representNum != representNext) {
				this.merge(representNum, representNext);
			}
		}
		return max;
	}

	private void merge(int num, Integer next) {
		int sizeNum = this.s[num];
		int sizeNext = this.s[next];
		int total = sizeNum + sizeNext;
		this.max = Math.max(max, total);
		if (sizeNum <= sizeNext) {// size并到next里
			this.p[num] = next;
			this.s[num] = 1;
			this.s[next] = total;
		} else {
			this.p[next] = num;
			this.s[next] = 1;
			this.s[num] = total;
		}
	}

	private Integer findNext2Num(int num) {
		if (this.s[num] == 0) {// 没有
			return null;
		}
		return this.findRepresent(num);
	}

	private int findRepresent(int num) {// 找num的代表
		if (this.s[num] == 0) { // 第一次来
			this.p[num] = num; // 自己代表自己
			this.s[num] = 1;
			return num;
		}
		// 不是第一次来， 一定有个代表
		int pstack = 0;
		int ans = 0;
		while ((ans = this.p[num]) != num) {
			this.stack[pstack++] = ans;
			num = ans;
		}
		while (pstack > 0) {
			this.p[this.stack[--pstack]] = ans;//
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
